﻿#include "binarytree.h"
#include <qthread>
#include <iostream>
#include <queue>
#include <time.h>
#include <stdlib.h>
#include <qdebug.h>
#include "malloc.h"
#include <deque>

using namespace std;

//Pstart是二叉树根结点在一行中的位置，一行最能打印124个字符，取其1/2。
//如果你的屏不够宽的话，可以输出文本文件里， aa.exe>>aa.txt
#define Pstart 62

void BinaryTreeNodeTest()
{
    qDebug()<<"----二叉树测试函数----";
    PBTree *T;
    CreateBTree(T,10);
    //打印
    PrintBTree(*T);
#if 1
    //二叉树遍历
    printf("%s",QString("前序遍历：").toLocal8Bit().data());
    PreOrderTraverse(*T);
    printf("\n");

    printf("%s",QString("中序遍历：").toLocal8Bit().data());
    InOrderTraverse(*T);
    printf("\n");

    printf("%s",QString("后序遍历：").toLocal8Bit().data());
    PostOrderTraverse(*T);
    printf("\n");

    printf("%s",QString("层序遍历：").toLocal8Bit().data());
    LevelOrferTraverse(*T);
    printf("\n");

    qDebug()<<"----测试高度深度叶子结点个数----";
    qDebug()<<"深度："<<Depth(*T);
    qDebug()<<"叶子结点个数："<<LeafCount(*T);
    qDebug()<<"所有结点个数："<<NodeCount(*T);
    qDebug()<<"度为1的结点个数："<<NodeOneCount(*T);
#endif

    //销毁二叉树
    int n=0;
    DestroyBTree(T,&n);
    qDebug()<<"销毁结点个数："<<n;
    qDebug()<<"----二叉树测试函数结束----";
}
//销毁
void DestroyBTree(PBTree*T,int *count){
    if(*T){
        if((*T)->left != NULL)
            DestroyBTree(&((*T)->left),count);
        if((*T)->right != NULL)
            DestroyBTree(&((*T)->right),count);

        free(*T);
        *T=NULL;
        (*count)+=1;
    }
}
//创建树
void CreateBTree(PBTree *T, int num)
{
    srand(time(NULL));

    char array[num];
    array[0]='A';
    for(int i=1;i<num;++i){
        int data=rand()%44;
        if(data>25 || data==0)
            array[i]='a';
        else
            array[i]='A'+data;
    }

    for(int i=0;i<num;++i)
        printf("%c ",array[i]);
    printf("\n");
    fflush(stdout);

    CreateBTreeSub(T,array,num);
}
void CreateBTreeSub(PBTree *T,char*array,int num)
{
    static int index=0;
    if(index==num-1){
        (*T)=NULL;
    }
    else{
        char data=array[index++];
        if(data=='a')
            (*T)=NULL;
        else{
            *T=(PBTree)malloc(sizeof(BTreeNode));
            if((*T)==NULL)
                return;
            (*T)->data=data;

            CreateBTreeSub(&(*T)->left,array,num);
            CreateBTreeSub(&(*T)->right,array,num);
        }
    }
}
//二叉树打印
void PrintBTree(PBTree T,const bool charFlag)//ture==char,false==int
{
    qDebug()<<"----打印二叉树---------------------------------------------------------";
    if(T==NULL){
        qDebug()<<"二叉树为空。";
        return;
    }

    PrintBTree2(T,2,charFlag);
    qDebug()<<"-------------------------------------------------------------------------";
}
//循环打印所有层的数据
#define MaxSize 100

char bra[]={"-/\\<"};
void PrintBTree2(PBTree t,const int h,const bool charFlag){
    int i;
    if(t!=NULL){
        PrintBTree2(t->right,h+1,charFlag);
        for(i=0;i<h;i++)putchar('\t');
        if(charFlag)
            printf("%c ",t->data);
        else
            printf("%d ",t->intData);

        putchar(bra[
                ((NULL!=(t->left))<<1)
                |(NULL!=(t->right))
                ]);
        putchar('\n');
        PrintBTree2(t->left,h+1,charFlag);
    }
}

#include <list>
using namespace std;
class DisplayInfo
{
public:
    int level;
    int pos;        //结点在屏幕中的绝对位置
    bool enter;
    int spaceNum;
};
void NatureDisplayTree(BTreeNode *root)
{
    int i;
    list<BTreeNode *>Q;
    list<DisplayInfo>QI;
    int screenWidth=64;
    int dataWidth=2;
    DisplayInfo info;    //将插入队列的结点的打印信息
    DisplayInfo preInfo; //队尾的结点的打印信息
    BTreeNode *curNode;    //   \\队列当前取出的结点
    DisplayInfo curInfo; //队列当前取出的结点的打印信息
    if(!root)
    {
        printf("Tree is empty !\n");
        return;
    }
    printf("Nature Display Tree:\n");
    Q.push_back(root);
    info.level=1;
    info.enter=true;
    info.spaceNum=screenWidth>>info.level;
    info.pos=info.spaceNum;
    QI.push_back(info);
    preInfo=info;
    while(Q.size())
    {
        curNode=Q.front();
        Q.pop_front();
        curInfo=QI.front();
        if(curInfo.enter)
            printf("\n\n");
        for (i=0;i<curInfo.spaceNum;i++)
            printf(" ");
        printf("%2d",curNode->data);
        QI.pop_front();
        if(curNode->left)
        {
            Q.push_back(curNode->left);
            info.level=curInfo.level+1;
            info.pos=curInfo.pos-(screenWidth>>info.level);
            if(info.level>preInfo.level)
            {
                info.enter=true;
                info.spaceNum=info.pos;
            }
            else
            {
                info.enter=false;
                info.spaceNum=info.pos-preInfo.pos;
            }
            info.spaceNum-=dataWidth;
            QI.push_back(info);
            preInfo=info;

        }
        if(curNode->right)
        {
            Q.push_back(curNode->right);
            info.level=curInfo.level+1;
            info.pos=curInfo.pos+(screenWidth>>info.level);
            if(info.level>preInfo.level)
            {
                info.enter=true;
                info.spaceNum=info.pos;
            }
            else
            {
                info.enter=false;
                info.spaceNum=info.pos-preInfo.pos;
            }
            info.spaceNum-=dataWidth;
            QI.push_back(info);
            preInfo=info;
        }

    }
    printf("\n");
}

void PreOrderTraverse(PBTree T)
{
    if(T==NULL)
        return;
    printf("%c  ",T->data);
    PreOrderTraverse(T->left);
    PreOrderTraverse(T->right);
}

void InOrderTraverse(PBTree T)
{
    if(T==NULL)
        return;
    InOrderTraverse(T->left);
    printf("%c  ",T->data);
    InOrderTraverse(T->right);
}

void PostOrderTraverse(PBTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->left);
    PostOrderTraverse(T->right);
    printf("%c  ",T->data);
}

void LevelOrferTraverse(PBTree T)
{
    if(T==NULL)
        return;

    deque<PBTree>dequePBTree;
    dequePBTree.push_back(T);

    while(dequePBTree.size()){
        PBTree pNode=dequePBTree.front();
        dequePBTree.pop_front();

        printf("%c ",pNode->data);

        if(pNode->left)
            dequePBTree.push_back(pNode->left);
        if(pNode->right)
            dequePBTree.push_back(pNode->right);
    }
}

size_t Depth(PBTree root)
{
    if(root==NULL)
        return 0;
    size_t left=Depth(root->left);
    size_t right=Depth(root->right);

    //树的高度是左右子树高度的最大值加1，加上根结点
    if(left>right)
        return left+1;
    else
        return right+1;
}

size_t LeafCount(PBTree root)
{
    if(root==NULL)
        return 0;
    if(root->left==NULL && root->right==NULL)
        return 1;
    else
        //叶子结点的个数就是左子树和右子树叶子结点的总和
        return LeafCount(root->left)+LeafCount(root->right);
}

size_t NodeCount(PBTree root)
{
    if(root==NULL)
        return 0;
    return 1+NodeCount(root->left)+NodeCount(root->right);
}

size_t NodeOneCount(PBTree root)
{
    if(root==NULL)
        return 0;
    if(root->left==NULL && root->right==NULL)
        return 0;
    else if(root->left!=NULL && root->right==NULL)
        return 1+NodeOneCount(root->left);
    else if(root->left==NULL && root->right!=NULL)
        return 1+NodeOneCount(root->right);
}

void QuestionNodeCount()
{
    qDebug()<<"请输入起始节点m,终止节点n：";
    while(true){
        int m,n;
        cin>>m>>n;
        if(m==0 && n==0)
            return;
        int count=1; //记数
        queue<int> intQueue;
        intQueue.push(m);
        while(!intQueue.empty()){
            int tmpM=intQueue.front();
            intQueue.pop();

            if(tmpM*2<=n){
                intQueue.push(tmpM*2);
                ++count;
            }
            if(tmpM*2+1 <=n){
                intQueue.push(tmpM*2+1);
                ++count;
            }
        }
        qDebug()<<"记数为："<<count;
    }
}

void QuestionNodeCount2()
{
    qDebug()<<"请输入起始节点m,终止节点n：";
    int m, n;
    while(scanf("%d %d",&m,&n)!= EOF){
        if(m==0 && n==0)
            return;
        qDebug()<<"记数为："<<QuestionNodeCount2Sub(m,n);
    }
}

int QuestionNodeCount2Sub(const int m, const int n)
{
    if(m>n)
        return 0;
    else
        return 1+
                QuestionNodeCount2Sub(m*2,n)+
                QuestionNodeCount2Sub(m*2+1,n);
}

void Q2_ReCreate_Test()
{
    qDebug()<<"----二叉树重建函数----";
    //    PBTree *T;
    BTNode *T;
    CreateBTree_Int(&T,10);
    //前序遍历
    vector<int>preVtr=Q2_PreOrder(T);
    printf("PreVtr:");
    for(auto &i:preVtr)
        printf("%d ",i);
    printf("\n");
    //中序遍历
    vector<int>inVtr=Q2_InOrder(T);
    printf("PreVtr:");
    for(auto &i:inVtr)
        printf("%d ",i);
    printf("\n");

    //打印
    PrintBTree(T,false);
    //销毁
    int count=0;
    DestroyBTree(&T,&count);
    if(count!=0)
        qDebug()<<"销毁了"<<count<<"个结点。";
    //重建函数
    BTNode *tree=Q2_ReCreate(preVtr,inVtr);
    if(tree!=NULL)
        qDebug()<<"创建成功。";
    else{
        qDebug()<<"创建失败。";
        return;
    }
    //打印
    PrintBTree(tree,false);
    //销毁
    count=0;
    DestroyBTree(&tree,&count);
    if(count!=0)
        qDebug()<<"销毁了"<<count<<"个结点。";
    qDebug()<<"----二叉树重建函数结束----";
}

void CreateBTree_Int(BTNode**T, const int num)
{
#if 0
    int *array=new int[num];
    if(array==NULL)
        return;
    srand(time(NULL));
    printf("Source array:");
    for(int i=0;i<num;++i){
        int intData=rand()%33;
        if(intData<9)
            intData=-1;

        array[i]=intData;
        printf("%d ",intData);
    }
    printf("\n");

    CreateBTreeRecursion_Int(T,array,num);

    delete[]array;
    array=NULL;
#endif
    vector<int>intVtr;
    vector<int>::iterator it;
    intVtr.push_back(99);
    for(int i=1;i<num;++i){
        int intData=rand()%33;
        if(intData<10)
            intVtr.push_back(-1);
        else{
            it=find(intVtr.begin(),intVtr.end(),intData);
            if(it==intVtr.end())
                intVtr.push_back(intData);
            else
                --i;
        }
    }

    printf("Source array:");
    for(auto &i:intVtr)
        printf("%d ",i);
    printf("\n");

    CreateBTreeRecursion_Int(T,intVtr);

    PrintBTree(*T,false);
}

void CreateBTreeRecursion_Int(BTNode **T, const vector<int>&intVtr)
{
    if(intVtr.empty())
        return;
    static int count=0;
    if(count >=intVtr.size()-1){
        (*T)=NULL;
        return;
    }

    int intData=intVtr[count++];
    if(intData==-1){
        (*T)=NULL;
        return;
    }
    else{
        (*T)=new BTNode;
        if((*T)==NULL)
            return;
        (*T)->intData=intData;

        //默认数据是前序遍历的数据，所以创建时也是使用前序的方式创建。
        CreateBTreeRecursion_Int(&((*T)->left),intVtr);
        CreateBTreeRecursion_Int(&((*T)->right),intVtr);
    }

}

vector<int> Q2_PreOrder(BTNode *root)
{
    static vector<int> intVtr;
    if(root==NULL)
        return intVtr;

    intVtr.push_back(root->intData);

    Q2_PreOrder(root->left);
    Q2_PreOrder(root->right);

    return intVtr;
}

vector<int> Q2_InOrder(BTNode *root)
{
    static vector<int> intVtr;
    if(root==NULL)
        return intVtr;

    Q2_InOrder(root->left);
    intVtr.push_back(root->intData);
    Q2_InOrder(root->right);

    return intVtr;
}

BTNode * Q2_ReCreate(vector<int> preVtr, vector<int> inVtr)
{
    if(preVtr.empty() || inVtr.empty())
        return NULL;
    BTNode *root=new  BTNode;
    if(root==NULL)
        return NULL;
    root->intData=preVtr[0];
    //printf("%d ",preVtr[0]);
    //前序遍历第一个结点是根结点，
    //中序遍历根结点左侧的都是根结点的左子树
    int leftCount=0; //左子树结点个数
    for(;leftCount<inVtr.size();++leftCount){
        if(inVtr[leftCount] == preVtr[0])
            break;
    }

    vector<int>leftPreVtr,rightPreVtr,leftInVtr,rightInVtr;
    int preIndex=1;  //略过第一个根结点

    for(int i=0;i<inVtr.size();++i){
        if(i<leftCount){
            leftPreVtr.push_back(preVtr[preIndex++]);
            leftInVtr.push_back(inVtr[i]);
        }
        else if(i>leftCount){
            rightPreVtr.push_back(preVtr[preIndex++]);
            rightInVtr.push_back(inVtr[i]);
        }
    }

    root->left=Q2_ReCreate(leftPreVtr,leftInVtr);
    root->right=Q2_ReCreate(rightPreVtr,rightInVtr);
    return root;
}

void Q3_HasSubtreeTest()
{
    const int Num=11;

    srand(time(NULL));
    vector<int>intVtr;
    vector<int>::iterator it;
    intVtr.push_back(99);
    for(int i=1;i<Num;++i){
        int intData=rand()%99;
        if(intData<22)
            intVtr.push_back(-1);
        else{
            it=find(intVtr.begin(),intVtr.end(),intData);
            if(it==intVtr.end())
                intVtr.push_back(intData);
            else
                --i;
        }
    }

    printf("Source array:");
    for(auto &i:intVtr)
        printf("%d ",i);
    printf("\n");

    vector<int>intVtr2;
    int j=0;
    for(int i=5;i<intVtr.size();++i)
        intVtr2.push_back(intVtr[i]);

    printf("Tree2 array:");
    for(auto &i:intVtr2)
        printf("%d ",i);
    printf("\n");

    BTNode *root1=NULL;
    CreateBTreeRecursion_Int(&root1,intVtr);
    qDebug()<<"Tree1 结点数:"<<NodeCount(root1);
    PrintBTree(root1,false);

    QThread::sleep(1);

    BTNode *root2=NULL;
    CreateBTreeRecursion_Int(&root1,intVtr2);
    qDebug()<<"Tree2 结点数:"<<NodeCount(root2);
    PrintBTree(root2,false);

    int count=0;
    DestroyBTree(&root1,&count);
    qDebug()<<"销毁了root1结点数："<<count;
    //    DestroyBTree(&root2,&count);
    //    qDebug()<<"销毁了root2结点数："<<count;
}

bool Q3_HasSubtree(BTNode *root1, BTNode *root2)
{
    if(root1==NULL || root2==NULL)
        return false;
    return (Q3_IsSubtree(root1,root2)||
            Q3_IsSubtree(root1->left,root2->left)||
            Q3_IsSubtree(root2->right,root2->right));
}
bool Q3_IsSubtree(BTNode *root1, BTNode *root2)
{
    if(root1==NULL)
        return false;
    if(root2==NULL)
        return true;
    if(root1->intData == root2->intData){
        return Q3_IsSubtree(root1->left,root2->left)&&
                Q3_IsSubtree(root1->right,root2->right);
    }else
        return false;
}

void Q4_Mirror(BTNode *root)
{
    if(root==NULL)
        return;
    BTNode *tmpNode=root->left;
    root->left=root->right;
    root->right=tmpNode;

    Q4_Mirror(root->left);
    Q4_Mirror(root->right);
}

void Q4_MirrorTest()
{
    BTNode *root=NULL;
    CreateBTree_Int(&root,10);
    PrintBTree(root,false);

    qDebug()<<"获取镜像";
    Q4_Mirror(root);
    PrintBTree(root,false);

    int count=0;
    DestroyBTree(&root,&count);
    qDebug()<<"销毁了结点个数："<<count;
}


void Q5_FindPathTest()
{
    BTNode *root=NULL;
    //    CreateBTree_Int(&root,10);

    int array[]={99,12,-1,33,-1,-1,43,75,32,-1,45,-1,94,-1,-1};
    size_t size=sizeof(array)/sizeof(int);
    vector<int>intVtr;
    printf("Source Array:");
    for(int i=0;i<size;++i){
        intVtr.push_back(array[i]);
        printf("%d ",array[i])   ;
    }
    printf("\n");
    CreateBTreeRecursion_Int(&root,intVtr);

    PrintBTree(root,false);

    vector<vector<int> >reVtr;
    reVtr=Q5_FindPath_recursion(root,94);
    printf("ReVtr:");
    for(int i=0;i<reVtr.size();++i)
        for(int j=0;j<reVtr[0].size();++j)
            printf("%d-",reVtr[i][j]);
    printf("\n");

    Destroy(&root);
}

////非递归版本
////思路：
//1.按先序遍历把当前节点cur的左孩子依次入栈同时保存当前节点，每次更新当前路径的和sum；
//2.判断当前节点是否是叶子节点以及sum是否等于expectNumber，如果是，把当前路径放入结果中。
//3.遇到叶子节点cur更新为NULL，此时看栈顶元素，如果栈顶元素的把栈顶元素保存在last变量中，
//同时弹出栈顶元素，当期路径中栈顶元素弹出，sum减掉栈顶元素，这一步骤不更改cur的值；
//4.如果步骤3中的栈顶元素的右孩子存在且右孩子之前没有遍历过，当前节点cur更新为栈顶的右孩子，此时改变cur=NULL的情况。

//#include <iostream>
//#include <vector>

//using namespace std;

//struct TreeNode{
//    int val;
//    TreeNode *left;
//    TreeNode *right;
//    TreeNode(int x) : val(x), left(NULL), right(NULL){}
//}

//vector<vector<int> > FindPath(TreeNode *root, int expectNumber){
//    vector<vector<int> > res;
//    if (root == NULL)
//        return res;
//    stack<TreeNode *> s;
//    s.push(root);
//    int sum = 0; //当前和
//    vector<int> curPath; //当前路径
//    TreeNode *cur = root; //当前节点
//    TreeNode *last = NULL; //保存上一个节点
//    while (!s.empty()){
//        if (cur == NULL){
//            TreeNode *temp = s.top();
//            if (temp->right != NULL && temp->right != last){ //右子树不为空且没有遍历过
//                cur = temp->right; //转向未遍历过的右子树
//            }else{    //右子树为空或者已经被遍历过
//                last = temp; //保存上一个已遍历的节点
//                s.pop();
//                curPath.pop_back(); //从当前路径删除
//                sum -= temp->val;
//            }  }
//        else{
//            s.push(cur);
//            sum += cur->val;
//            curPath.push_back(cur->val);
//            if (cur->left == NULL && cur->right == NULL && sum == expectNum){
//                res.push_back(curPath);
//            }
//            cur = cur->left; //先序遍历，左子树先于右子树
//        }
//    }
//    return res;
//}

vector<vector<int> > Q5_FindPath_recursion(BTNode *root, int expectNumber)
{
    vector<vector<int> > reIntVtr;//保存多条路径
    if(root==NULL)
        return reIntVtr;

    vector<int>intVtr;//保存一条路径中的所有结点的值
    Q5_FindPath_recursion_sub(root,expectNumber,&intVtr,&reIntVtr);
    return reIntVtr;
}

void Q5_FindPath_recursion_sub(BTNode *root, int expectNumber, vector<int> *intVtr,vector<vector<int> > *reIntVtr)
{
    if(root==NULL || intVtr==NULL || reIntVtr==NULL)
        return;
    //若当前结点是叶子结点，同时值等于约定值时，把值保存到路径中
    if(root->intData==expectNumber && root->left==NULL && root->right==NULL){
        intVtr->push_back(root->intData);
        reIntVtr->push_back((*intVtr));
        intVtr->pop_back();
    }
    else{//如果以上要求不满足，将当前结点值放入路径中，再判断当前结点的左右子树的情况。
        intVtr->push_back(root->intData);

        if(root->left!=NULL)//当左子树不为空，遍历左子树
            Q5_FindPath_recursion_sub(root->left,expectNumber,intVtr,reIntVtr);
        if(root->right!=NULL)
            Q5_FindPath_recursion_sub(root->right,expectNumber,intVtr,reIntVtr);
        //删除当前结点，向上判断父节点的情况。
        intVtr->pop_back();
    }
}

void Destroy(BTNode **T)
{
    if(*T==NULL || T==NULL){
        qDebug()<<"销毁失败，树为空。";
        return ;
    }
    int count=0;
    DestroyBTree(T,&count);
    qDebug()<<"销毁结点个数："<<count;
}
